package com.xie.leetcode.string;

//383. 赎金信
//        为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
//
//        给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
//
//        如果可以构成，返回 true ；否则返回 false 。
//
//        magazine 中的每个字符只能在 ransomNote 中使用一次。
//
//
//
//        示例 1：
//
//        输入：ransomNote = "a", magazine = "b"
//        输出：false
//        示例 2：
//
//        输入：ransomNote = "aa", magazine = "ab"
//        输出：false
//        示例 3：
//
//        输入：ransomNote = "aa", magazine = "aab"
//        输出：true
//
//
//        提示：
//
//        1 <= ransomNote.length, magazine.length <= 105
//        ransomNote 和 magazine 由小写英文字母组成

import java.util.HashMap;
import java.util.Map;

/**
 * @author xiezhendong
 * @date 2021/12/04
 */
public class CanConstruct {

    public static void main(String[] args) {
        CanConstruct canConstruct = new CanConstruct();
        System.out.println(canConstruct.canConstruct("a", "b"));
        System.out.println(canConstruct.canConstruct("aa", "ab"));
        System.out.println(canConstruct.canConstruct("aa", "aab"));
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        Map<String, Integer> cMap = new HashMap<>();
        for (char c : magazine.toCharArray()) {
            cMap.merge(String.valueOf(c), 1, Integer::sum);
        }
        for (char c : ransomNote.toCharArray()) {
            if (cMap.get(String.valueOf(c)) != null) {
                cMap.put(String.valueOf(c), cMap.get(String.valueOf(c)) - 1);
            } else {
                cMap.put(String.valueOf(c), -1);
            }
            if (cMap.get(String.valueOf(c)) < 0) {
                return false;
            }
        }
        return true;
    }
}
